package com.aqie.arithmetic.sort;

import com.aqie.libs.StdRandom;

/**
 * 三路快排
 */
public class Quick3way extends SortTest{

    @Override
    public void sort(Comparable[] a) {
        //
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int l, int h){
        if (h <= l) return;
        int lt = l, i = l + 1, gt = h;
        Comparable v = a[l];
        while (i <= gt){
            int cmp = a[i].compareTo(v);
            if (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else i++;
        }
        sort(a, l, lt - 1);
        sort(a, gt + 1, h);
    }

    public static void main(String[] args) {
        new Quick3way().process(10000);
    }
}
